package com.codebo.homiematchbackend.utils;

import org.springframework.stereotype.Service;

@Service
public class SelfUtil
{
    /**
     * 计算两字符串的编辑距离（Levenshtein distance）
     * 时间复杂度 O(m*n)，空间复杂度 O(min(m,n))
     */
    public int editDistance(String s, String t)
    {
        if (s == null)
        {
            s = "";
        }
        if (t == null)
        {
            t = "";
        }
        int m = s.length();
        int n = t.length();
        if (m == 0) return n;
        if (n == 0) return m;

        /* 保证 s 永远是较短的那一行，进一步降低空间 */
        if (m > n)
        {
            String tmp = s;
            s = t;
            t = tmp;
            m = s.length();
            n = t.length();
        }

        /* 提前一次性申请数组，循环内不再 new */
        int[] prev = new int[m + 1];
        int[] curr = new int[m + 1];

        /* 第一行：0..m */
        for (int i = 0; i <= m; i++) prev[i] = i;

        /* 按行 DP */
        for (int j = 1; j <= n; j++)
        {
            curr[0] = j;
            char tc = t.charAt(j - 1);
            for (int i = 1; i <= m; i++)
            {
                int cost = (s.charAt(i - 1) == tc) ? 0 : 1;
                /* 三种操作取最小 */
                curr[i] = Math.min(
                        Math.min(prev[i] + 1,      // delete
                                curr[i - 1] + 1), // insert
                        prev[i - 1] + cost); // substitute
            }
            /* 滚动数组：curr -> prev */
            int[] tmp = prev;
            prev = curr;
            curr = tmp;
        }
        return prev[m];
    }
}
